#pragma once
#include<iostream>
#include"BasicType.h"
#include"MemUtil.h"
using namespace std;

enum NodeType{LEVELSTART, LEVELEND, INDEX, DATA};

template<class K, class V>//K V 这里只能是指针
class Node{
public:
    K key;
    V val;
    NodeType nodeType;
    int32_t level;
    Node<K, V>* lastNode;
    Node<K, V>* nextNode;
    Node<K, V>* upNode;
    Node<K, V>* downNode;

    bool isNormalNodeType(const NodeType& nt){
        return nt == INDEX || nt == DATA;
    }

    void initParam(const K k, const V v, const NodeType& nt, const int32_t& lv,
                   Node<K, V>* lNode, Node<K, V>* nNode, Node<K, V>* uNode, Node<K, V>* dNode){
        this->key = k;
        this->val = v;
        this->nodeType = nt;
        this->level = lv;
        this->lastNode = lNode;
        this->nextNode = nNode;
        this->upNode = uNode;
        this->downNode = dNode;
    }

    Node(const NodeType& nt, const int32_t& lv,
         Node<K, V>* lNode, Node<K, V>* nNode, Node<K, V>* uNode, Node<K, V>* dNode){
        if(isNormalNodeType(nt)){
            throw string("type error");
        }
        initParam(nullptr, nullptr, nt, lv, lNode, nNode, uNode, dNode);
    }

    Node(const K k, const int32_t& lv,
         Node<K, V>* lNode, Node<K, V>* nNode, Node<K, V>* uNode, Node<K, V>* dNode){
        initParam(k, nullptr, INDEX, lv, lNode, nNode, uNode, dNode);
    }

    Node(const K k, const V v, const int32_t& lv,
         Node<K, V>* lNode, Node<K, V>* nNode, Node<K, V>* uNode, Node<K, V>* dNode){
        initParam(k, v, DATA, lv, lNode, nNode, uNode, dNode);
    }


    bool isNormalNode(){
        return isNormalNodeType(nodeType);
    }

    //析构函数里面都是同步释放 仅在最头部控制异步
    ~Node(){
        if(level == 0){ //当为数据节点时才释放 索引节点里面的key指针和数据节点的key是同一份
            MemUtil::clearPtrMem(key);
            MemUtil::clearPtrMem(val);
        }
    }
};


//K V 这里只能是指针  //索引节点的key和数据节点的key是同一份数据减少key的拷贝
template<class K, class V>  //*K需要重载 == <    *V需要重载 ==
class SkipList{
private:
    //数据层为0层
    //每一层前后有start end 节点，不算做统计数量
    vector<int32_t> levelCounts;
    vector<Node<K, V>*> levelStarts;
    vector<Node<K, V>*> levelEnds;
    int32_t levelMultiple;

    bool compareK(const K k1, const K k2) const {
        return basicCmp(k1, k2);
    }

    bool equalsK(const K k1, const K k2) const {
        if(MemUtil::pairJudgeNull(k1, k2))
            return false;
        return basicEqu(k1, k2);
    }

    bool equalsV(const V v1, const V v2) const {
        if(MemUtil::pairJudgeNull(v1, v2))
            return false;
        return *v1 == *v2;
    }

    void initSkipList(const int32_t& levelMultiple){
        this->levelMultiple = levelMultiple;
        addLevel();
    }

    //有序列表初始化datalevel 调用时需保证skipList为空 nodeVec有序
    void initDataLevel(const vector<Node<K, V>*>& nodeVec){
        Node<K, V>* node = getTopStartNode();
        Node<K, V>* endNode = node->nextNode;
        for(Node<K, V>* nextNode : nodeVec){
            //连接到前一个节点上
            levelLinkNode(node, nextNode);
            node = nextNode;
        }
        //将最后一个数据节点与levelEnd链接
        levelLinkNode(node, endNode);
        //更新数据节点个数
        levelCounts[0] = nodeVec.size();
    }

    //在数据层初始化完毕后调用
    void initIndex(){
        for(int32_t tmpLevel = 0; checkNeedInsertIndex(tmpLevel); tmpLevel++){
            addLevel();
            //添加的第一个节点和最后一个节点
            Node<K, V>* upStartNode = nullptr;
            Node<K, V>* upEndNode = nullptr;
            //遍历层节点 为层节点添加索引节点
            Node<K, V>* node = levelStarts[tmpLevel]->nextNode;
            int32_t levelCount = levelCounts[tmpLevel];
            int32_t insertLevel = tmpLevel + 1;
            for(int32_t tmpInd = 0; tmpInd < levelCount; tmpInd++, node = node->nextNode){
                //tmpInd模二余一时添加（每两个节点添加一个索引）
                if((tmpInd % levelMultiple) == 0){
                    Node<K, V>* upNode = new Node<K, V>(node->key, insertLevel, nullptr, nullptr, nullptr, nullptr);
                    //与下层节点和上一个添加的节点连接
                    verticalLinkNode(node, upNode);
                    if(upEndNode != nullptr){
                        levelLinkNode(upEndNode, upNode);
                    }
                    //更新添加的第一个节点和最后一个节点
                    if(upStartNode == nullptr){
                        upStartNode = upNode;
                    }
                    upEndNode = upNode;
                }
            }
            //将新创建的索引节点与头尾节点链接
            Node<K, V>* upLevelStartNode = levelStarts[insertLevel];
            Node<K, V>* upLevelEndNode = upLevelStartNode->nextNode;
            levelLinkNode(upLevelStartNode, upStartNode);
            levelLinkNode(upEndNode, upLevelEndNode);
            //更新节点个数
            levelCounts[insertLevel] = levelCount / levelMultiple;
        }
    }

    //只用于彻底删除所有节点 和删除只有头尾节点的一行（不涉及数据寻路） 所以不需要把指向他们的指针置null
    void clearLevelNode(Node<K, V>* eraseNode){
        for(Node<K, V>* nextEraseNode; eraseNode != nullptr; eraseNode = nextEraseNode){
            nextEraseNode = eraseNode->nextNode;
            //就一个节点 就同步了（异步释放有一定开销） 大量释放只出现在 资源池释放资源的时候 那个操作已经是异步的
            MemUtil::clearPtrMem(eraseNode);
        }
    }

    //在floorNode节点之后插入insNode
    void levelInsertNode(Node<K, V>* lastNode, Node<K, V>* insNode){
        //由于插入时在左上节点后面插入新节点 所以nextNode不会为null
        Node<K, V>* nextNode = lastNode->nextNode;
        insNode->lastNode = lastNode;
        insNode->nextNode = nextNode;
        lastNode->nextNode = insNode;
        nextNode->lastNode = insNode;
    }

    void levelLinkNode(Node<K, V>* lastNode, Node<K, V>* insNode){
        lastNode->nextNode = insNode;
        insNode->lastNode = lastNode;
    }

    //水平方向移除节点连接
    void levelEraseNode(Node<K, V>* eraseNode){
        //eraseNode的指针不置null 不影响释放
        //不会用这个函数删除首尾节点 所以lastNode nextNode不会为null
        Node<K, V>* lastNode = eraseNode->lastNode;
        Node<K, V>* nextNode = eraseNode->nextNode;
        lastNode->nextNode = nextNode;
        nextNode->lastNode = lastNode;
    }

    //在downNode节点上方添加一个insNode节点
    //downNode的upNode应为null
    void verticalLinkNode(Node<K, V>* downNode, Node<K, V>* insNode){
        insNode->downNode = downNode;
        downNode->upNode = insNode;
    }

    void verticalUnlinkNode(Node<K, V>* eraseNode){  //eraseNode的upNode应为null
        //不会用这个函数删除底层节点 所以downNode不会为Null
        eraseNode->downNode->upNode = nullptr;
    }

    //清除node开始 向上连接的所有节点
    //移除的节点需要装进vec里，后续一起释放。
    void eraseVerticalLinkedNode(vector<Node<K, V>*>& eraseNodeVec, Node<K, V>* node){
        for(int32_t i = node->level; node != nullptr; node = node->upNode, i++){
            levelEraseNode(node);
            eraseNodeVec.push_back(node);
            levelCounts[i]--;
            //数量--后 判断是否是顶层 如果是的话尝试释放顶层
            if(i == levelCounts.size() - 1){
                removeLevel();
            }
        }
    }



    //增加一层 增加数据层 索引层都适配
    void addLevel(){
        Node<K, V>* levelStart = new Node<K, V>(LEVELSTART, levelCounts.size(), nullptr, nullptr, nullptr, nullptr);
        Node<K, V>* levelEnd = new Node<K, V>(LEVELEND, levelCounts.size(), nullptr, nullptr, nullptr, nullptr);
        //将新一层首尾互相连接
        levelLinkNode(levelStart, levelEnd);
        //将新一层头部尾部与原本的顶层头部尾部互相连接
        if(!levelCounts.empty()){
            verticalLinkNode(levelStarts.back(), levelStart);
            verticalLinkNode(levelEnds.back(), levelEnd);
        }
        //更新开始结束节点列表
        levelStarts.push_back(levelStart);
        levelEnds.push_back(levelEnd);
        //更新层节点个数列表
        levelCounts.push_back(0);
    }

    //尝试移除顶层节点
    void removeLevel(){
        if(levelCounts.back() != 0 || levelCounts.size() == 1){
            return; //若最上层节点个数不为0 或者 到数据层了 直接返回
        }
        //释放顶层
        clearLevelNode(getTopStartNode());
        //更新层头指针列表
        levelStarts.pop_back();
        levelEnds.pop_back();
        //更新层节点个数列表
        levelCounts.pop_back();
    }

    //检测tmpLevel的上一层是否需要插入索引节点
    bool checkNeedInsertIndex(const int32_t& tmpLevel) const {
        //当前层级个数小于levelMultiple不需要有上层索引 直接返回false
        const int32_t& tmpLevelCount = levelCounts[tmpLevel];
        if(tmpLevelCount < levelMultiple){
            return false;
        }
        //需要有上层索引但是上层索引根本不存在 返回true
        const int32_t& insertLevel = tmpLevel + 1;
        if(levelCounts.size() == insertLevel){
            return true;
        }
        return levelCounts[insertLevel] < (tmpLevelCount / levelMultiple);
    }

    //检测tmpLevel的上一层是否需要删除索引节点
    bool checkNeedEraseIndex(const int32_t& tmpLevel) const {
        //eraseLevel已经超出范围时 直接返回false
        const int32_t& eraseLevel = tmpLevel + 1;
        if(eraseLevel == levelCounts.size()){
            return false;
        }
        return levelCounts[eraseLevel] > (levelCounts[tmpLevel] / levelMultiple);
    }

    //传入的tmpNode不能是顶层节点
    Node<K, V>* getUpFloorNode(Node<K, V>* tmpNode) const {
        //由于首节点的upNode一定不为空 tmpNode在为null前一定有upNode
        for(; tmpNode->upNode == nullptr; tmpNode = tmpNode->lastNode);
        return tmpNode->upNode;
    }

    //传入的tmpNode不能是顶层节点
    Node<K, V>* getUpNeighbourNodeForErase(Node<K, V>* tmpNode, const bool& getFloor) const {
        while(tmpNode != nullptr){
            Node<K, V>* upNode = tmpNode->upNode;
            if(upNode != nullptr && upNode->isNormalNode() && upNode->upNode == nullptr){
                return upNode;  //当此节点不是首尾节点且没有上层节点才可以删除
            }
            tmpNode = getFloor ? tmpNode->lastNode : tmpNode->nextNode;
        }
        return nullptr;
    }

    //传入的tmpNode不能是顶层节点
    Node<K, V>* getUpFloorOrUpCeilingNodeForErase(Node<K, V>* tmpNode) const {
        Node<K, V>* eraseNode = getUpNeighbourNodeForErase(tmpNode->lastNode, true);//不包括tmpNode节点 floor方向从lastNode开始
        if(eraseNode != nullptr){
            return eraseNode;
        }
        eraseNode = getUpNeighbourNodeForErase(tmpNode->nextNode, false);//不包括tmpNode节点 ceiling方向从nextNode开始
        if(eraseNode != nullptr){
            return eraseNode;
        }
        throw string("error");
    }

    Node<K, V>* getNeighbourNodeAsInsert(Node<K, V>* tmpNode, bool getFloor) const {
        while (tmpNode != nullptr) {
            if(tmpNode->upNode == nullptr && tmpNode->isNormalNode()){
                return tmpNode;
            }
            tmpNode = getFloor ? tmpNode->lastNode : tmpNode->nextNode;
        }
        return nullptr;
    }

    Node<K, V>* getFloorOrCeilingNodeAsInsert(Node<K, V>* tmpNode) const {
        Node<K, V>* insNode = getNeighbourNodeAsInsert(tmpNode->lastNode, true);//不包括tmpNode节点 floor方向从lastNode开始
        if(insNode != nullptr){
            return insNode;
        }
        insNode = getNeighbourNodeAsInsert(tmpNode->nextNode, false);//不包括tmpNode节点 ceiling方向从nextNode开始
        if(insNode != nullptr){
            return insNode;
        }
        throw string("error");
    }

    //返回key val都符合的节点， 如果没有返回大于等于key的第一个节点。
    Node<K, V>* getProbNode(K targetKey, V targetVal) const {
        Node<K, V>* floorNode = getLastFloorNode(targetKey);
        for(Node<K, V>* node = floorNode; equalsK(node->key, targetKey); node = node->lastNode){
            if(equalsV(node->val, targetVal)){
                return node;
            }
        }
        return floorNode;
    }


    //添加数据节点后维护索引节点
    void maintainIndexAfterInsert(Node<K, V>* lastInsNode){
        for(int32_t tmpLevel = lastInsNode->level; checkNeedInsertIndex(tmpLevel); tmpLevel++){
            int32_t insertLevel = tmpLevel + 1;
            if(insertLevel == levelCounts.size()){
                addLevel();
            }
            Node<K, V>* insNode = new Node<K, V>(lastInsNode->key, insertLevel, nullptr, nullptr, nullptr, nullptr);
            levelInsertNode(getUpFloorNode(lastInsNode), insNode);
            //lastInsNode 也是才创建的不应有upNode
            verticalLinkNode(lastInsNode, insNode);
            levelCounts[insertLevel]++;
            lastInsNode = insNode;
        }
    }


    void maintainIndexAfterErase(vector<Node<K, V>*>& eraseNodeVec, Node<K, V>* lastEraseNode){
        for(int32_t tmpLevel = lastEraseNode->level; checkNeedEraseIndex(tmpLevel); tmpLevel++){
            int32_t eraseLevel = tmpLevel + 1;
            Node<K, V>* eraseNode = getUpFloorOrUpCeilingNodeForErase(lastEraseNode);
            levelEraseNode(eraseNode);
            verticalUnlinkNode(eraseNode);
            eraseNodeVec.push_back(eraseNode);
            levelCounts[eraseLevel]--;
            //数量--后 判断是否是顶层 如果是的话尝试释放顶层
            if(eraseLevel == levelCounts.size() - 1){
                removeLevel();
            }
            lastEraseNode = eraseNode;
        }
    }


public:

    SkipList(const int32_t& levelMultiple = 2){
        initSkipList(levelMultiple);
    }

    SkipList(const vector<Node<K, V>*>& nodeVec, const int32_t& levelMultiple = 2){
        initSkipList(levelMultiple);
        initDataLevel(nodeVec);
        initIndex();
    }

    ~SkipList(){
        clear();
    }

    void clear(){
        for(Node<K, V>* node : levelStarts){
            clearLevelNode(node);
        }
    }

    int32_t getSize() const {
        return levelCounts.front();
    }

    int32_t getLevelMultiple() const {
        return levelMultiple;
    }

    Node<K, V>* getTopStartNode() const {
        return levelStarts.back();
    }

    Node<K, V>* getTopEndNode() const {
        return levelEnds.back();
    }

    Node<K, V>* getDataStartNode() const {
        return levelStarts.front()->nextNode;
    }

    Node<K, V>* getDataEndNode() const {
        return levelEnds.front()->lastNode;
    }

    //返回大于或等于key的第一个节点
    Node<K, V>* getFirstCeilingNode(K targetKey) const {
        Node<K, V>* tmpNode = getTopEndNode();
        while(true){
            Node<K, V>* lastNode = tmpNode->lastNode;
            if(lastNode->nodeType != LEVELSTART && (compareK(targetKey, lastNode->key) || equalsK(targetKey, lastNode->key))){
                tmpNode = lastNode;
            }
            else{
                if(tmpNode->level == 0){
                    return tmpNode;
                }
                tmpNode = tmpNode->downNode;
            }
        }
    }

    //返回小于或等于key的最后一个节点
    Node<K, V>* getLastFloorNode(K targetKey) const {
        //没有元素的三种情况：1太大 2太小 3大小正常但是没有 tmpNode最终都会到最后一层节点
        Node<K, V>* tmpNode = getTopStartNode();
        while(true){
            Node<K, V>* nextNode = tmpNode->nextNode;
            if(nextNode->nodeType != LEVELEND && (compareK(nextNode->key, targetKey) || equalsK(nextNode->key, targetKey))){
                tmpNode = nextNode;
            }
            else{
                if(tmpNode->level == 0){
                    return tmpNode;
                }
                tmpNode = tmpNode->downNode;
            }
        }
    }

    //满足符合的所有Val
    vector<V> find(K targetKey) const {
        vector<V> resVec;
        for(Node<K, V>* node = getLastFloorNode(targetKey); equalsK(node->key, targetKey); node = node->lastNode){
            resVec.push_back(node->val);
        }
        return resVec;
    }

    //
    Node<K, V>* find(K targetKey, V targetVal) const {
        for(Node<K, V>* node = getLastFloorNode(targetKey); equalsK(node->key, targetKey); node = node->lastNode){
            if(equalsV(node->val, targetVal)){
                return node;
            }
        }
        return nullptr;
    }

    bool insert(const K key, const V val){
        //如果已有key val都符合的节点返回该节点, 否则获取大于等于key的第一个节点
        Node<K, V>* node = getProbNode(key, val);
        if(equalsK(node->key, key) && equalsV(node->val, val)){
            return false;
        }
        //创建新节点 插入新节点 0层为数据层
        Node<K, V>* insNode = new Node<K, V>(key, val, 0, nullptr, nullptr, nullptr, nullptr);
        levelInsertNode(node, insNode);
        levelCounts[0]++;
        maintainIndexAfterInsert(insNode);
        return true;
    }

    bool erase(const K key, const V val){
        //如果已有key val都符合的节点返回该节点, 否则获取大于等于key的第一个节点
        Node<K, V>* eraseNode = getProbNode(key, val);
        if(!equalsK(eraseNode->key, key) || !equalsV(eraseNode->val, val)){
            return false;
        }
        vector<Node<K, V>*> eraseNodeVec;
        eraseVerticalLinkedNode(eraseNodeVec, eraseNode);
        //维护同时删除节点的这些层的平衡 如3,6变成2,5(同时-1)
        if(eraseNodeVec.size() > 1 && checkNeedInsertIndex(0)){
            //在删除节点附近找一个上面没有索引的节点
            Node<K, V>* insNode = getFloorOrCeilingNodeAsInsert(eraseNode);
            //依据这个节点建索引节点
            maintainIndexAfterInsert(insNode);
        }
        //维护最后删除节点的一层和它上一层的平衡
        maintainIndexAfterErase(eraseNodeVec, eraseNodeVec.back());
        MemUtil::clearVecMem(eraseNodeVec);
        return true;
    }

};
